package com.leetcode.根据算法进行分类.单调栈相关;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author: ZhouBert
 * @date: 2021/2/26
 * @description: 901. 股票价格跨度
 * https://leetcode-cn.com/problems/online-stock-span/
 */
public class B_901_股票价格跨度 {

	public static void main(String[] args) {

	}

	/**
	 * 从题目中可以了解到：
	 * 调用次数很高，此时应该避免保存所有的数据，而是通过更加高效的结构来处理
	 * ->
	 * 使用两个栈完成：
	 * 除了记录数据的栈，还有一个栈用来记录数据当前“值的数值”
	 */
	class StockSpanner {

		private Deque<Integer> priceStack = new ArrayDeque<Integer>();

		private Deque<Integer> valueStack = new ArrayDeque<Integer>();

		public StockSpanner() {

		}

		public int next(int price) {
			//本身代表1
			int value = 1;
			while (!priceStack.isEmpty() && priceStack.peekLast() <= price) {
				//当 栈非空 && 栈顶元素 【小于等于】 新进元素时
				priceStack.removeLast();
				Integer lastValue = valueStack.removeLast();
				value+=lastValue;
			}
			priceStack.addLast(price);
			valueStack.addLast(value);
			return value;
		}
	}
}
